package com.tocici.recommender;

import com.tocici.service.IUserBehaviorService;
import lombok.RequiredArgsConstructor;
import org.springframework.stereotype.Component;

import java.util.*;

public class Apriori {


    public static List<Map<Set<String>, Integer>> apriori(List<Set<String>> transactions, double minSupport) {
        List<Map<Set<String>, Integer>> result = new ArrayList<>();

        // 计算最小支持次数
        int minCount = (int) Math.ceil(minSupport);

        // 生成频繁1-项集
        Map<Set<String>, Integer> frequent1Itemset = getFrequent1Itemsets(transactions, minCount);
        result.add(frequent1Itemset);

        // 迭代生成更高阶项集
        int k = 2;
        while (true) {
            Map<Set<String>, Integer> candidates = generateCandidates(result.get(k-2), k);
            Map<Set<String>, Integer> frequentItemset = calculateSupport(candidates, transactions, minCount);

            if (frequentItemset.isEmpty()) break;

            result.add(frequentItemset);
            k++;
        }

        return result;
    }

    // 生成频繁1-项集
    private static Map<Set<String>, Integer> getFrequent1Itemsets(List<Set<String>> transactions, int minCount) {
        Map<String, Integer> itemCount = new HashMap<>();

        // 统计单个项出现次数
        for (Set<String> transaction : transactions) {
            for (String item : transaction) {
                itemCount.put(item, itemCount.getOrDefault(item, 0) + 1);
            }
        }

        // 过滤满足最小支持度的项
        Map<Set<String>, Integer> frequentItems = new HashMap<>();
        for (Map.Entry<String, Integer> entry : itemCount.entrySet()) {
            if (entry.getValue() >= minCount) {
                Set<String> itemSet = new HashSet<>();
                itemSet.add(entry.getKey());
                frequentItems.put(itemSet, entry.getValue());
            }
        }

        return frequentItems;
    }

    // 生成候选k-项集
    private static Map<Set<String>, Integer> generateCandidates(Map<Set<String>, Integer> prevFrequent, int k) {
        Map<Set<String>, Integer> candidates = new HashMap<>();

        // 使用前一次频繁项集生成候选项集
        List<Set<String>> itemsets = new ArrayList<>(prevFrequent.keySet());

        // 两两组合生成候选项
        for (int i = 0; i < itemsets.size(); i++) {
            for (int j = i+1; j < itemsets.size(); j++) {
                Set<String> union = new HashSet<>(itemsets.get(i));
                union.addAll(itemsets.get(j));

                if (union.size() == k && isValidCandidate(union, itemsets, k-1)) {
                    candidates.put(union, 0);
                }
            }
        }

        return candidates;
    }

    // 验证候选集的k-1子集是否都是频繁的
    private static boolean isValidCandidate(Set<String> candidate, List<Set<String>> prevFrequent, int subsetSize) {
        List<Set<String>> subsets = getSubsets(candidate, subsetSize);

        for (Set<String> subset : subsets) {
            if (!prevFrequent.contains(subset)) {
                return false;
            }
        }
        return true;
    }

    // 获取集合的所有指定大小的子集
    static List<Set<String>> getSubsets(Set<String> set, int size) {
        List<Set<String>> subsets = new ArrayList<>();
        List<String> items = new ArrayList<>(set);
        int n = items.size();

        int[] indices = new int[size];
        for (int i = 0; i < size; i++) {
            indices[i] = i;
        }

        while (true) {
            Set<String> subset = new HashSet<>();
            for (int index : indices) {
                subset.add(items.get(index));
            }
            subsets.add(subset);

            int i;
            for (i = size-1; i >= 0; i--) {
                if (indices[i] != i + n - size) break;
            }
            if (i < 0) break;

            indices[i]++;
            for (int j = i+1; j < size; j++) {
                indices[j] = indices[j-1] + 1;
            }
        }

        return subsets;
    }

    // 计算候选项集的支持度
    private static Map<Set<String>, Integer> calculateSupport(Map<Set<String>, Integer> candidates,
                                                              List<Set<String>> transactions,
                                                              int minCount) {
        // 统计候选项出现次数
        for (Set<String> transaction : transactions) {
            for (Set<String> candidate : candidates.keySet()) {
                if (transaction.containsAll(candidate)) {
                    candidates.put(candidate, candidates.get(candidate) + 1);
                }
            }
        }

        // 过滤满足最小支持度的项集
        Map<Set<String>, Integer> frequentItems = new HashMap<>();
        for (Map.Entry<Set<String>, Integer> entry : candidates.entrySet()) {
            if (entry.getValue() >= minCount) {
                frequentItems.put(entry.getKey(), entry.getValue());
            }
        }

        return frequentItems;
    }
}
